/*
 * Code from http://www.gurge.com/amd/old/java/GIFEncoder/
 * 
 * From FAQ:
 * 
 * 3. Can I copy your code? Distribute it? Modify it? 
 * There are no restrictions whatsoever on my code. Feel free to copy it, modify it, and distribute it however you see fit. 
 * You can even take my name off and write in your own. This code is free for the taking. No, you don't have to mail me 
 * for permission. Just do it.
 */
package dijjer.util;

import java.io.IOException;
import java.io.OutputStream;

/**
 * @author ian
 * 
 * To change the template for this generated type comment go to Window - Preferences - Java - Code Generation - Code and
 * Comments
 */
public class GIFEncoder {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	private final short _width;
	private final short _height;
	private int _numColors;
	private byte[] _pixels;
	private byte[] _colors;
	private ScreenDescriptor _sd;
	private ImageDescriptor _id;

	/**
	 * Construct a GIFEncoder. The constructor will convert the image to an indexed color array. <B>This may take some
	 * time. </B>
	 * <P>
	 * 
	 * Each array stores intensity values for the image. In other words, r[x][y] refers to the red intensity of the
	 * pixel at column x, row y.
	 * <P>
	 * 
	 * @param r
	 *                   An array containing the red intensity values.
	 * @param g
	 *                   An array containing the green intensity values.
	 * @param b
	 *                   An array containing the blue intensity values.
	 */
	public GIFEncoder(byte r[][], byte g[][], byte b[][]) {
		_width = (short) (r.length);
		_height = (short) (r[0].length);
		toIndexedColor(r, g, b);
	}

	/**
	 * Writes the image out to a stream in the GIF file format. This will be a single GIF87a image, non-interlaced, with
	 * no background color. <B>This may take some time. </B>
	 * <P>
	 * 
	 * @param output
	 *                   The stream to output to. This should probably be a buffered stream.
	 * 
	 * @exception IOException
	 *                        Will be thrown if a write operation fails.
	 */
	public void write(OutputStream output) throws IOException {
		BitUtils.writeString(output, "GIF87a");
		ScreenDescriptor sd = new ScreenDescriptor(_width, _height, _numColors);
		sd.write(output);
		output.write(_colors, 0, _colors.length);
		ImageDescriptor id = new ImageDescriptor(_width, _height, ',');
		id.write(output);
		byte codesize = BitUtils.bitsNeeded(_numColors);
		if (codesize == 1) ++codesize;
		output.write(codesize);
		LZWCompressor.LZWCompress(output, codesize, _pixels);
		output.write(0);
		id = new ImageDescriptor((byte) 0, (byte) 0, ';');
		id.write(output);
		output.flush();
	}

	private void toIndexedColor(byte r[][], byte g[][], byte b[][]) {
		_pixels = new byte[_width * _height];
		_colors = new byte[256 * 3];
		int colornum = 0;
		for (int x = 0; x < _width; ++x) {
			for (int y = 0; y < _height; ++y) {
				int search;
				for (search = 0; search < colornum; ++search)
					if (_colors[search * 3] == r[x][y] && _colors[search * 3 + 1] == g[x][y]
							&& _colors[search * 3 + 2] == b[x][y]) break;
				if (search > 255) throw new RuntimeException("Too many colors.");
				_pixels[y * _width + x] = (byte) search;
				if (search == colornum) {
					_colors[search * 3] = r[x][y];
					_colors[search * 3 + 1] = g[x][y];
					_colors[search * 3 + 2] = b[x][y];
					++colornum;
				}
			}
		}
		_numColors = 1 << BitUtils.bitsNeeded(colornum);
		byte copy[] = new byte[_numColors * 3];
		System.arraycopy(_colors, 0, copy, 0, _numColors * 3);
		_colors = copy;
	}
}


class BitFile {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	private final OutputStream _output;
	private final byte[] _buffer;
	private int _index;
	private int _bitsLeft;

	public BitFile(OutputStream output) {
		_output = output;
		_buffer = new byte[256];
		_index = 0;
		_bitsLeft = 8;
	}

	public void flush() throws IOException {
		int numBytes = _index + (_bitsLeft == 8 ? 0 : 1);
		if (numBytes > 0) {
			_output.write(numBytes);
			_output.write(_buffer, 0, numBytes);
			_buffer[0] = 0;
			_index = 0;
			_bitsLeft = 8;
		}
	}

	public void writeBits(int bits, int numbits) throws IOException {
		int numBytes = 255;
		do {
			if ((_index == 254 && _bitsLeft == 0) || _index > 254) {
				_output.write(numBytes);
				_output.write(_buffer, 0, numBytes);
				_buffer[0] = 0;
				_index = 0;
				_bitsLeft = 8;
			}
			if (numbits <= _bitsLeft) {
				_buffer[_index] |= (bits & ((1 << numbits) - 1)) << (8 - _bitsLeft);
				_bitsLeft -= numbits;
				numbits = 0;
			} else {
				_buffer[_index] |= (bits & ((1 << _bitsLeft) - 1)) << (8 - _bitsLeft);
				bits >>= _bitsLeft;
				numbits -= _bitsLeft;
				_buffer[++_index] = 0;
				_bitsLeft = 8;
			}
		} while (numbits != 0);
	}
}


class LZWStringTable {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	private final static int RES_CODES = 2;
	private final static short HASH_FREE = (short) 0xFFFF;
	private final static short NEXT_FIRST = (short) 0xFFFF;
	private final static int MAXBITS = 12;
	private final static int MAXSTR = (1 << MAXBITS);
	private final static short HASHSIZE = 9973;
	private final static short HASHSTEP = 2039;

	private final byte[] _strChr;
	private final short[] _strNxt;
	private final 	short[] _strHsh;
	private short _numStrings;

	public LZWStringTable() {
		_strChr = new byte[MAXSTR];
		_strNxt = new short[MAXSTR];
		_strHsh = new short[HASHSIZE];
	}

	public int addCharString(short index, byte b) {
		int hshidx;
		if (_numStrings >= MAXSTR) return 0xFFFF;
		hshidx = hash(index, b);
		while (_strHsh[hshidx] != HASH_FREE)
			hshidx = (hshidx + HASHSTEP) % HASHSIZE;
		_strHsh[hshidx] = _numStrings;
		_strChr[_numStrings] = b;
		_strNxt[_numStrings] = (index != HASH_FREE) ? index : NEXT_FIRST;
		return _numStrings++;
	}

	public short findCharString(short index, byte b) {
		int hshidx, nxtidx;
		if (index == HASH_FREE) return b;
		hshidx = hash(index, b);
		while ((nxtidx = _strHsh[hshidx]) != HASH_FREE) {
			if (_strNxt[nxtidx] == index && _strChr[nxtidx] == b) return (short) nxtidx;
			hshidx = (hshidx + HASHSTEP) % HASHSIZE;
		}
		return (short) 0xFFFF;
	}

	public void clearTable(int codesize) {
		_numStrings = 0;
		for (int q = 0; q < HASHSIZE; q++) {
			_strHsh[q] = HASH_FREE;
		}
		int w = (1 << codesize) + RES_CODES;
		for (int q = 0; q < w; q++)
			addCharString((short) 0xFFFF, (byte) q);
	}

	static public int hash(short index, byte lastbyte) {
		return (((short) (lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
	}
}


class LZWCompressor {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	public static void LZWCompress(OutputStream output, int codesize, byte toCompress[]) throws IOException {

		byte c;
		short index;
		int clearcode, endofinfo, numbits, limit, errcode;
		short prefix = (short) 0xFFFF;
		BitFile bitFile = new BitFile(output);
		LZWStringTable strings = new LZWStringTable();
		clearcode = 1 << codesize;
		endofinfo = clearcode + 1;
		numbits = codesize + 1;
		limit = (1 << numbits) - 1;
		strings.clearTable(codesize);
		bitFile.writeBits(clearcode, numbits);
		for (int loop = 0; loop < toCompress.length; ++loop) {
			c = toCompress[loop];
			if ((index = strings.findCharString(prefix, c)) != -1)
				prefix = index;
			else {
				bitFile.writeBits(prefix, numbits);
				if (strings.addCharString(prefix, c) > limit) {
					if (++numbits > 12) {
						bitFile.writeBits(clearcode, numbits - 1);
						strings.clearTable(codesize);
						numbits = codesize + 1;
					}
					limit = (1 << numbits) - 1;
				}
				prefix = (short) ((short) c & 0xFF);
			}
		}
		if (prefix != -1) bitFile.writeBits(prefix, numbits);
		bitFile.writeBits(endofinfo, numbits);
		bitFile.flush();
	}
}


class ScreenDescriptor {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	public short localScreenWidth_, localScreenHeight_;
	private byte byte_;
	public byte backgroundColorIndex_, pixelAspectRatio_;

	public ScreenDescriptor(short width, short height, int numColors) {
		localScreenWidth_ = width;
		localScreenHeight_ = height;
		setGlobalColorTableSize((byte) (BitUtils.bitsNeeded(numColors) - 1));
		setGlobalColorTableFlag((byte) 1);
		setSortFlag((byte) 0);
		setColorResolution((byte) 7);
		backgroundColorIndex_ = 0;
		pixelAspectRatio_ = 0;
	}

	public void write(OutputStream output) throws IOException {
		BitUtils.writeWord(output, localScreenWidth_);
		BitUtils.writeWord(output, localScreenHeight_);
		output.write(byte_);
		output.write(backgroundColorIndex_);
		output.write(pixelAspectRatio_);
	}

	public void setGlobalColorTableSize(byte num) {
		byte_ |= (num & 7);
	}

	public void setSortFlag(byte num) {
		byte_ |= (num & 1) << 3;
	}

	public void setColorResolution(byte num) {
		byte_ |= (num & 7) << 4;
	}

	public void setGlobalColorTableFlag(byte num) {
		byte_ |= (num & 1) << 7;
	}
}


class ImageDescriptor {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	private final byte _separator;
	private final short _leftPosition;
	private final short _topPosition;
	private final short _width;
	private final short _height;
	private byte _byte;

	public ImageDescriptor(short width, short height, char separator) {
		_separator = (byte) separator;
		_leftPosition = 0;
		_topPosition = 0;
		_width = width;
		_height = height;
		setLocalColorTableSize((byte) 0);
		setReserved((byte) 0);
		setSortFlag((byte) 0);
		setInterlaceFlag((byte) 0);
		setLocalColorTableFlag((byte) 0);
	}

	public void write(OutputStream output) throws IOException {
		output.write(_separator);
		BitUtils.writeWord(output, _leftPosition);
		BitUtils.writeWord(output, _topPosition);
		BitUtils.writeWord(output, _width);
		BitUtils.writeWord(output, _height);
		output.write(_byte);
	}

	public void setLocalColorTableSize(byte num) {
		_byte |= (num & 7);
	}

	public void setReserved(byte num) {
		_byte |= (num & 3) << 3;
	}

	public void setSortFlag(byte num) {
		_byte |= (num & 1) << 5;
	}

	public void setInterlaceFlag(byte num) {
		_byte |= (num & 1) << 6;
	}

	public void setLocalColorTableFlag(byte num) {
		_byte |= (num & 1) << 7;
	}
}


class BitUtils {

	public static final String VERSION = "$Id: GIFEncoder.java 2 2008-03-21 14:33:03Z ian.clarke $";

	public static byte bitsNeeded(int n) {
		byte ret = 1;
		if (n-- == 0) {
			return 0;
		}
		while ((n >>= 1) != 0) {
			++ret;
		}
		return ret;
	}

	public static void writeWord(OutputStream output, short w) throws IOException {
		output.write(w & 0xFF);
		output.write((w >> 8) & 0xFF);
	}

	static void writeString(OutputStream output, String string) throws IOException {
		for (int loop = 0; loop < string.length(); ++loop) {
			output.write((byte) (string.charAt(loop)));
		}
	}
}
